package org.example.sward.tooffer;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;

public class Offer38 {

        List<String> res = new LinkedList<>();
        char[] c;
        public String[] permutation(String s) {
            c = s.toCharArray();
            dfs(0);
            for (String str : res){
                System.out.println(str);
            }
            return res.toArray(new String[res.size()]);
        }
        void dfs(int x) {
            if(x == c.length - 1) {
                // 添加排列方案
                res.add(String.valueOf(c));
                return;
            }
            HashSet<Character> set = new HashSet<>();
            for(int i = x; i < c.length; i++) {
                // 重复，因此剪枝
                if(set.contains(c[i])){
                    continue;
                }
                set.add(c[i]);
                // 交换，将 c[i] 固定在第 x 位
                swap(i, x);
                // 开启固定第 x + 1 位字符
                dfs(x + 1);
                // 恢复交换
                swap(i, x);
            }
        }
        void swap(int a, int b) {
            char tmp = c[a];
            c[a] = c[b];
            c[b] = tmp;
        }

    public static void main(String[] args) {
        Offer38 offer38 = new Offer38();
        String[] res =  offer38.permutation("abc");
        System.out.println(res);

    }
}
